kamuszhou的博客，转载请注明URL。 现代大规模集成电路图（VLSI）非常庞大，当我们希望用多个FPGA仿真一个VLSI时，需要把VLSI在满足一些约束条件的情况下切割成多个小部分，每个部分都可以装进一个FPGA。 这个问题抽象成数学模型，实际上就是一个超图分割的问题。在超图分割领域有一篇发表于1982年的论文，名字是”A Linear-Time Heuristic for Improving Network Partitions”。这篇论文提出了一种改进的“超图二分问题”算法，简称为FM算法。虽然在1982年这篇论文发表时，“超图分割”算法领域已经发展了近十年。但这篇论文似乎有着近乎祖师爷级论文的地位，相当多的后期该领域的论文都会引用这篇文章。论文发表之后该领域继续发展出的“层次化超图多分割”算法可以看成是FM算法发展而来。该算法中涉及到的概念和思路是后续算法的基础，是很好的该领域入门学习的资料。 （更多超图及超图分割的基础概念请自行搜索，本博客主要解读论文） 论文的下载地址： https://ieeexplore.ieee.org/document/1585498 在论文的摘要部分论述到：本文提出了一种启发式的，利用最小割(mincut)的迭代算法解决超图二分问题。该算法在最坏情况下的时间复杂度也是线性的。在实际应用中，绝大多数情况下，该算法都只需要很少次数的迭代。算法有三个特点： 1. 超图被分成两个Block。每次移动一个结点把它从原来的Block移往另一个Block。同时维持两个Block的平衡。重要的是，这个平衡不是基于每个Block中的结点数量，而是更一般的size of block的概念，它考虑到了每个结点的权重是不一样的。 2. 利用一个相当高效的数据结构，可以在O(1)常数时间复杂度内找到需要移动的最佳结点。 3. 在移动了某个结点后，再高效地更新受上次移动影响的结点的信息(即论文后面会提到的结点的gain值)。这第三个特点亦在论文的Introduction中被再次提到，作者认为这是该论文的主要贡献(main contribution). 术语及基本概念 n(i): 当i是超边的编号时，n(i)定义为每个超边上的结点数目。 s(i)或p(i): 当i表示结点时，s(i)或p(i)表示结点上的PIN数目，即结点一共跟多个条超边有连接，更多时候亦称为结点的size。 邻居结点： 如果两个结点至少能通过一条超边连接，即为邻居结点。 A，B： 代表超图二分割后的两个BLOCK。 ｜A｜： |A| = \sum_{i=i}^{n}{s(i)} 即Block A的size定义为Block A中所有的结点的size的连加。 A(n)或B(n)： n表示编号为n的边，A(n)则表示该条n在Block A中的结点数。 cut: 在A和B中都有结点的超边。 cutstate: 一条超边是不是cut（后来发展成多分割问题中的cutsize）。 cell gains: 当移动一个结点到另一个BLOCK时，cut减少的数目。 维持平衡 最容易想到的是就是使超图二分割后的两个BLOCK中的结点数量大致相同。不过，可以稍微变复杂一点，即考虑每个结点的权重。 * W ＝ |A| + … Continue reading Fiduccia Mattheyses算法(即FM算法)的论文解读